// 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
// 注意：k可以大于链表长度

struct ListNode *get_listlen(struct ListNode *head) {
    int count = 0;
    while (head) {
        head = head->next;
        count++;
    }
    return  count;
} 

struct ListNode* rotateRight(struct ListNode* head, int k){
    if (head == NULL) return NULL;
    struct ListNode *dummy = malloc(sizeof(*dummy));
    dummy->next = head; 
    struct ListNode *cur = dummy;

    int len = get_listlen(head);
    int num = len - k % len;
    while (num--) {
        cur = cur->next;
    }


    // cur->next为新的链表头
    struct ListNode *p = cur;
    while (p->next != NULL) {   // 找到链表尾
        p = p->next;
    }

    p->next = head;
    head = cur->next;
    cur->next = NULL;
    free(dummy);
    // 其它思路：可以先连接成环，再分割。
    return head;
}